Feedback Vertex Set hat Anwendungen im VLSI-Chipdesign, in der Programmverifizierung und bei der Beseitigung einer Verklemmung (deadlock). Das Problem bleibt sogar für gerichteten Graphen mit maximalem Eingangsgrad 2 und für gerichtete ebene Graphen mit maximalem Eingangsgrad 3 NP-vollständig. Das Problem, Kanten zu löschen, um einen ungericht...